package org.drake.refactor.skill.inline;

import java.util.*;

public class Graph {
    private Vertex vertex;
    private Queue<Vertex> queue;
    private List<Character> bfsRes;
    private LinkedList<Vertex> stack;
    private List<Character> dfsRes;
    private Set<Vertex> bfsVisited;
    private Set<Vertex> dfsVisited;

    class Vertex {
        Character value;
        List<Vertex> adj;

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj instanceof Vertex) {
                return Objects.equals(this.value, ((Vertex) obj).value);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return this.value.hashCode();
        }
    }

    void bfs (Graph graph) {
        initBfs(graph);
        doBfs();
    }

    private void doBfs() {
        while (!queue.isEmpty()) {
            Vertex vertex1 = queue.poll();
            bfsRes.add(vertex1.value);

            for (Vertex v : vertex1.adj) {
                if (!bfsVisited.contains(v)) {
                    queue.offer(v);
                    bfsVisited.add(v);
                }
            }
        }
    }

    private void initBfs(Graph graph) {
        bfsRes = new ArrayList<>();
        queue = new LinkedList<>();
        bfsVisited = new HashSet<>();

        queue.add(graph.vertex);
        bfsVisited.add(graph.vertex);
    }

    // 回溯
    void dfs(Graph graph) {
        initDfs(graph);
        doDfs();
    }

    private void doDfs() {
        while (!stack.isEmpty()) {
            Vertex vertex = stack.pop();
            dfsRes.add(vertex.value);

            for (Vertex v : vertex.adj) {
                if (!dfsVisited.contains(v)) {
                    stack.add(v);
                    dfsVisited.add(v);
                }
            }
        }
    }

    private void initDfs(Graph graph) {
        dfsRes = new ArrayList<>();
        stack = new LinkedList<>();
        dfsVisited = new HashSet<>();

        stack.add(graph.vertex);
        dfsVisited.add(graph.vertex);
    }
}
